package com.linyaonan.leetcode.medium._11;

/**
 * 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
 *
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 返回容器可以储存的最大水量。
 *
 * 说明：你不能倾斜容器。
 *
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
 *
 * @author: Lin
 * @date: 2024/3/13
 */
public class ContainerWithMostWater {

    public int maxArea(int[] height) {
        if (height == null || height.length == 1) {
            return 0;
        }
        // 只有两个柱子，那么长度为1，高度为较低的数值
        if (height.length == 2) {
            return Math.min(height[0], height[1]);
        }

        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while(left < right) {
            int min;
            int width = right - left;
            if (height[left] <= height[right]) {
                min = height[left];
                left++;
            } else {
                min = height[right];
                right--;
            }
            max = Math.max(max, (width * min));
        }

        return max;
    }

    /**
     * 通过观察可以发现，该问题还是双指针问题，当两个木板不一样高时，低的这一根决定了储水量，
     * 那么只有移动低的这一根木板才有可能出现木板高于较低的木板从而总水量变高（因为宽度减一）
     *
     * 所以归类还是双指针移动问题，每一次移动较低木板，并且移动时记录储水量即可
     * @param height
     * @return
     */
    public int maxArea2(int[] height) {
        // 1. 异常边界
        if (height == null || height.length == 0 || height.length == 1) {
            return 0;
        }
        if (height.length == 2) {
            return Math.min(height[0], height[1]);
        }
        // 2. 使用双指针
        int l = 0;
        int r = height.length - 1;
        int max = 0;
        while (l < r) {
            int w = r - l;
            int h = 0;
            // 向右移动
            if (height[l] < height[r]) {
                h = height[l];
                l++;
            } else {
                h = height[r];
                r--;
            }
            max = Math.max(max, w * h);
        }

        return max;
    }

}
